Latency-sensitive processing and real-time analytics are expected to account for significant fraction of processing cycles in hyperscale data centers, which may include cloud-based computing centers. Real-time analytics is a growing market, which is estimated to reach over $13 billion by 2018. Bitmap operations are important building blocks in many real-time analytics operations. Bitmaps store bit-arrays of users, events, webpages, and so on. Furthermore, bitmaps facilitate many efficient queries such as, for example, tracking of events, or tracking of number of unique visitors, data mining, and so on. Common real-time analytics operations on bitmaps include POPCOUNT operations (discussed below) and logical bitwise operations such as OR, AND, XOR, NAND, and the like.
A common use-case in real-time analytics is maintenance of various statistics of website usage via large bitmaps. A POPCOUNT (or population count) operation counts the number of ones (1s) in a bit sequence. Its usage has traditionally been in cryptography, but has been gaining popularity in recent years in the real-time data analytics domain. For example, a website can track webpage visit per user through a bit vector—with each “1” bit corresponding to one user. Thus, counting the number of unique visitors for a given webpage is essentially popcounting the bit vector. As an illustration, in case of a website with 4 million users, the bit vector size needed to account for all the users is on the order of 512 kilo bytes (KB) (=4 Mb (mega bits)).
It is noted here that the capitalized term “POPCOUNT,” its non-capitalized version “popcount,” and the term “bitcount” may be used interchangeably herein for ease of discussion. Similarly, for ease of discussion, the terms “bitmap” and “bit vector” may be used interchangeably below as essentially referring to a sequence of bits.